<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /* 
        1. 核心逻辑: 
            1.1 'abc' 'cc''abd' 比较每一个字符串的最后一个字符 再比较倒数第二个，以此类推 直到比较第一个
        1. 具体的细节：
            1.1 需要知道最长的字符串是多少 进而知道要总共比较多少趟
            1.2 'abc' 'ab' 如果像ab这样少了一个字符，就用 0 替代 ，0的ASCLL值是比'a'小的['a'.charCodeAt('0')是97 而0是48]
            【难点】 如果实现 缺失的部分用0去补足
            1.3 每一层里面使用计数排序 需要countArray 计数的数组，需要进行往前累加一位，需要倒序遍历原始数列，根据统计数列的值找到位置进行赋值
            每次排序完以后需要进行数组的赋值 给到下一次的拷贝使用【必须用到深拷贝】
        2. 时间复杂度 O( n(m + k)) m+k表示原始数组和统计数组的遍历，n表示最大的字符数量
        3. 空间复杂度  O(m+n)m是统计数组 n是结果数组的值
        */
        function findMaxValue(arr) {
            let max = arr[0].length
            for (let item of arr) {
                if (item.length > max) {
                    max = item.length
                }
            }
            return max
        }
        function radixSort(nums) {
            // 1. 第一步找到 数组里面字符串的最大长度
            let max = findMaxValue(nums)
            // 2. 声明最终的排序数组 sortArray + countArray()
            let sortArray = new Array(nums.length)
            let ASCII_RANGE = 128

            // 3. 我们从最后一个字符开始往前面遍历
            for (let k = max - 1; k >= 0; k--) {
                // 4. 写好getCharIndex方法
                // 5. 根据ASCLL方法得出的值，去countArray里面++
                let countArray = new Array(ASCII_RANGE).fill(0)
                for (let i = nums.length - 1; i >= 0; i--) {
                    let index = getCharIndex(nums[i], k)
                    countArray[index]++
                }
                // 6. 最终的countArray数组进行倒序相加
                for (let j = 1; j < countArray.length; j++) {
                    countArray[j] = countArray[j] + countArray[j - 1]
                }
                // 7.我们从nums的最后一个数组开始倒着往前面遍历
                for (let m = 1; m < nums.length; m--) {
                    let index = getCharIndex(nums[m], k)
                    let position = countArray[index] - 1
                    sortArray[position] = nums[m]
                    countArray[index]--
                }
                nums = JSON.parse(JSON.stringify(sortArray))
            }
            return nums
        }

        // 获取字符串第k位字符的ACSLL数
        function getCharIndex(str, k) {
            // 如果最长字符比如'aaa' 但是一个字符串只有 'aa' 那就第三位返回的是0
            if (str.length < (k + 1)) {
                return 0
            }
            return str.charCodeAt(k)
        }
        let arr2 = ['qd', 'abc', 'qwe', 'hhh', 'a', 'cws', 'ope']
        console.log(radixSort(arr2));
    </script>
</body>

</html>